package cn.edu.njust.alg;

public class SortImpl {

	public static void merge(int[] a, int begin, int mid, int end) {
		int[] b = new int[end - begin + 1];
		int i = begin;
		int j = mid + 1;
		int k = 0;
		while (i <= mid && j <= end) {
			if (a[i] > a[j]) {
				b[k] = a[i];
				i++;
			} else {
				b[k] = a[j];
				j++;
			}
			k++;
		}
		if (i > mid) {
			for (int s = 0; s < b.length - k; s++) {
				b[k + s] = a[j + s];
			}
		} else {
			for (int s = 0; s < b.length - k; s++) {
				b[k + s] = a[i + s];
			}
		}
		for (int s = 0; s < b.length; s++) {
			a[begin + s] = b[s];
		}
	}

	public static void mergesort(int[] a, int begin, int end) {
		if (begin >= end) {
			return;
		} else {
			int mid = (begin + end) / 2;
			mergesort(a, begin, mid);
			mergesort(a, mid + 1, end);
			merge(a, begin, mid, end);
		}
	}

	/**
	 * @param a
	 * @param p
	 * @param q
	 */
	public static void swap(int[] a, int p, int q) {

		int tmp = a[p];
		a[p] = a[q];
		a[q] = tmp;
	}

	public static int partion(int[] a, int begin, int end) {
		int key = a[begin];
		int p = begin;
		int q = end + 1;
		while (true) {
			while (a[++p] > key && p<end)
				;
			while (a[--q] < key)
				;
			if (p >= q)
				break;
			swap(a, p, q);
		}
		a[begin] = a[q];
		a[q]=key;
		
		return q;
	}

	public static void qsort(int[] a, int begin, int end) {
		if (begin < end) {
			int q = partion(a, begin, end);
			qsort(a, begin, q - 1);
			qsort(a, q + 1, end);
		}

	}

	public static void main(String[] args) {

		int[] a = { 3, 45, 6, 78, 454, 23, 23, 747, 538, 453 };

		qsort(a, 0, a.length - 1);
		for (int i : a) {
			System.out.println(i);
		}
	}

}
